import java.util.*;
import java.lang.*;

class MoveTimerTask2 extends TimerTask
{
	int[] moveCoord = new int[3];
	int[] newMove;
	public MoveTimerTask2(int[] _newMove)
	{
		newMove = _newMove;
	}
	public void run()
	{
		//System.out.println("------------------------------------------------");
		//System.out.print("Sending Move\n");
		//System.out.println("-------------------------------------------------");
		//put coords in move
		newMove[0] = moveCoord[0];
		newMove[1] = moveCoord[1];
		newMove[2] = moveCoord[2];
	}
	public void updateMoveCoord(int[] _moveCoord)
	{
		moveCoord = _moveCoord;
	}
}

public class BetterPlayer3D extends Player 
{
	String color;
	int pieces;
	int player;
	int playerSpace;
	int otherPlayerSpace;
	int boardSize;
	MinMaxTree decisionTree;
	final int[][][] initialBoardState;
	int[][][] boardValues;

    public BetterPlayer3D(int _boardSize, int p) 
    {
    	super(p, 'c');
    	pieces = 0;
    	boardSize = _boardSize;
		player = p;
		if(player == 0)
		{
			color = "green";
			playerSpace = -1;
			otherPlayerSpace = 1;
		}
		else
		{
			color = "blue";
			playerSpace = 1;
			otherPlayerSpace = -1;
		}
		initialBoardState = new int[_boardSize][_boardSize][_boardSize];
		for (int i = 0; i < _boardSize; i++)
		{
			for (int j = 0; j < _boardSize; j++)
			{
				for (int k = 0; k < _boardSize; k++)
				{
					initialBoardState[i][j][k] = 0;
				}
			}
		}
		/*will be black at:
		(n/2, n/2+1, n/2)
		(n/2+1, n/2, n/2)
		(n/2, n/2, n/2+1)
		(n/2+1, n/2+1, n/2+1)
		and white at:
		(n/2, n/2, n/2)
		(n/2+1, n/2+1, n/2)
		(n/2, n/2+1, n/2+1)
		(n/2+1, n/2, n/2+1)
		*/
		initialBoardState[(_boardSize-1)/2][((_boardSize-1)/2)+1][(_boardSize-1)/2] = 1;
		initialBoardState[((_boardSize-1)/2)+1][(_boardSize-1)/2][(_boardSize-1)/2] = 1;
		initialBoardState[(_boardSize-1)/2][(_boardSize-1)/2][((_boardSize-1)/2)+1] = 1;
		initialBoardState[((_boardSize-1)/2)+1][((_boardSize-1)/2)+1][((_boardSize-1)/2)+1] = 1;
		
		initialBoardState[(_boardSize-1)/2][(_boardSize-1)/2][(_boardSize-1)/2] = -1;
		initialBoardState[((_boardSize-1)/2)+1][((_boardSize-1)/2)+1][(_boardSize-1)/2] = -1;
		initialBoardState[(_boardSize-1)/2][((_boardSize-1)/2)+1][((_boardSize-1)/2)+1] = -1;
		initialBoardState[((_boardSize-1)/2)+1][(_boardSize-1)/2][((_boardSize-1)/2)+1] = -1;
		
		//populate board values
		boardValues = new int[_boardSize][_boardSize][_boardSize];
		//default values
		for (int i = 0; i < _boardSize; i++)
		{
			for (int j = 0; j < _boardSize; j++)
			{
				for (int k = 0; k < _boardSize; k++)
				{
					boardValues[i][j][k] = 1;
				}
			}
		}
		//side values
		for (int i = 0; i < _boardSize; i++)
		{
			for (int j = 0; j < _boardSize; j++)
			{
				boardValues[0][i][j] = 2;
				boardValues[i][0][j] = 2;
				boardValues[i][j][0] = 2;
				boardValues[_boardSize-1][i][j] = 2;
				boardValues[i][_boardSize-1][j] = 2;
				boardValues[i][j][_boardSize-1] = 2;
			}
		}
		//edge values
		for (int i = 0; i < _boardSize; i++)
		{
			boardValues[0][0][i] = 3;
			boardValues[boardSize-1][0][i] = 3;
			boardValues[0][i][0] = 3;
			boardValues[boardSize-1][i][0] = 3;
			boardValues[i][0][0] = 3;
			boardValues[i][boardSize-1][0] = 3;
			boardValues[_boardSize-1][_boardSize-1][i] = 3;
			boardValues[0][boardSize-1][i] = 3;
			boardValues[_boardSize-1][i][_boardSize-1] = 3;
			boardValues[0][i][boardSize-1] = 3;
			boardValues[i][_boardSize-1][_boardSize-1] = 3;
			boardValues[i][0][boardSize-1] = 3;
		}
		//corners
		boardValues[0][0][0] = 50;
		boardValues[0][0][_boardSize-1] = 50;
		boardValues[0][_boardSize-1][0] = 50;
		boardValues[0][_boardSize-1][_boardSize-1] = 50;
		boardValues[_boardSize-1][0][0] = 50;
		boardValues[_boardSize-1][0][_boardSize-1] = 50;
		boardValues[_boardSize-1][_boardSize-1][0] = 50;
		boardValues[_boardSize-1][_boardSize-1][_boardSize-1] = 50;
		//c and x Squares
		boardValues[1][0][0] = -10;
		boardValues[1][1][0] = -10;
		boardValues[0][1][0] = -10;
		boardValues[0][1][1] = -10;
		boardValues[0][0][1] = -10;
		boardValues[1][0][1] = -10;
		boardValues[1][1][1] = -25;
		
		boardValues[boardSize-2][0][0] = -10;
		boardValues[boardSize-2][1][0] = -10;
		boardValues[boardSize-2][0][1] = -10;
		boardValues[boardSize-1][1][0] = -10;
		boardValues[boardSize-1][0][1] = -10;
		boardValues[boardSize-1][1][1] = -10;
		boardValues[boardSize-2][1][1] = -25;
		
		boardValues[boardSize-2][boardSize-1][0] = -10;
		boardValues[boardSize-1][boardSize-2][0] = -10;
		boardValues[boardSize-1][boardSize-1][1] = -10;
		boardValues[boardSize-2][boardSize-2][0] = -10;
		boardValues[boardSize-1][boardSize-2][1] = -10;
		boardValues[boardSize-2][boardSize-1][1] = -10;
		boardValues[boardSize-2][boardSize-2][1] = -25;
		
		boardValues[0][boardSize-2][0] = -10;
		boardValues[0][boardSize-1][1] = -10;
		boardValues[1][boardSize-1][1] = -10;
		boardValues[1][boardSize-2][0] = -10;
		boardValues[0][boardSize-2][1] = -10;
		boardValues[1][boardSize-1][1] = -10;
		boardValues[1][boardSize-2][1] = -25;
		
		boardValues[boardSize-1][0][boardSize-2] = -10;
		boardValues[boardSize-2][0][boardSize-1] = -10;
		boardValues[boardSize-1][1][boardSize-1] = -10;
		boardValues[boardSize-2][0][boardSize-2] = -10;
		boardValues[boardSize-2][1][boardSize-1] = -10;
		boardValues[boardSize-1][1][boardSize-2] = -10;
		boardValues[boardSize-2][1][boardSize-2] = -25;
		
		boardValues[1][0][boardSize-1] = -10;
		boardValues[0][1][boardSize-1] = -10;
		boardValues[0][0][boardSize-2] = -10;
		boardValues[1][0][boardSize-2] = -10;
		boardValues[0][1][boardSize-2] = -10;
		boardValues[1][1][boardSize-1] = -10;
		boardValues[1][1][boardSize-2] = -25;
		
		boardValues[0][boardSize-1][boardSize-2] = -10;
		boardValues[0][boardSize-2][boardSize-1] = -10;
		boardValues[1][boardSize-1][boardSize-1] = -10;
		boardValues[0][boardSize-2][boardSize-2] = -10;
		boardValues[1][boardSize-1][boardSize-2] = -10;
		boardValues[1][boardSize-2][boardSize-1] = -10;
		boardValues[1][boardSize-2][boardSize-2] = -25;
		
		boardValues[boardSize-1][boardSize-1][boardSize-2] = -10;
		boardValues[boardSize-1][boardSize-2][boardSize-1] = -10;
		boardValues[boardSize-1][boardSize-2][boardSize-2] = -10;
		boardValues[boardSize-2][boardSize-1][boardSize-1] = -10;
		boardValues[boardSize-2][boardSize-1][boardSize-2] = -10;
		boardValues[boardSize-2][boardSize-2][boardSize-1] = -10;
		boardValues[boardSize-2][boardSize-2][boardSize-2] = -25;
		/*
		System.out.print("print state\n");
		for (int a = 0; a < boardSize; a++)
		{
			for (int b = 0; b < boardSize; b++)
			{
				System.out.print(initialBoardState[b][a]);
				System.out.print(" ");
			}
			System.out.print("\n");
		}
		*/
		decisionTree = new MinMaxTree<int[][][]>(initialBoardState, 3, 1);
		/*
		//if you are second player, set up decision tree
		if (color == "blue")
		{
			decisionTree = new MinMaxTree<int[][][]>(initialBoardState, 3, 1);
			MinMaxNode rootNode = decisionTree.getRootNode();
			List<int[]> moves = getValidMoves(initialBoardState, 1);
			//add child node for each move
			for (int i = 0; i < moves.size(); i++)
			{
				int[][][] tmpstate = copyState(initialBoardState);
				int[][][] newState = createState(tmpstate, (int[])moves.get(i), 1);
				List aMove = new ArrayList(3);
				aMove.add(((int[])(moves.get(i)))[0]);
				aMove.add(((int[])(moves.get(i)))[1]);
				aMove.add(((int[])(moves.get(i)))[2]);
				MinMaxNode<int[][][]> aChild = new MinMaxNode(newState, aMove, 3, 0);
				rootNode.addChild(aChild);
				//evalUtility(aChild);
				//System.out.print("Utility: ");
				//System.out.println(aChild.getUtilValue());
				
			}
		}*/
    }
    
    public void makeMove3D(int boardSize, int[][][] boardState, int[] lastMove, Long maxTime, int[] newMove)
    {
    	Long timeUp = System.currentTimeMillis() + 3000;
    	Timer moveTimer = new Timer();
    	MoveTimerTask2 task = new MoveTimerTask2(newMove);
		moveTimer.schedule(task, 2000);
		
    	decisionTree = new MinMaxTree<int[][][]>(boardState, 3, 1);
    	MinMaxNode<int[][][]> rootNode = decisionTree.getRootNode();
    	List<int[]> moves = getValidMoves(boardState, 0);
    	for (int i = 0; i < moves.size(); i++)
    	{
    		int[][][] newState = new int[boardSize][boardSize][boardSize];
    		newState = copyState(boardState);
    		newState = createState(newState, moves.get(i), 0);
    		List aMove = new ArrayList(3);
    		aMove.add(moves.get(i)[0]);
    		aMove.add(moves.get(i)[1]);
    		aMove.add(moves.get(i)[2]);
    		MinMaxNode<int[][][]> aChild = new MinMaxNode<int[][][]>(newState, aMove, 3, 1);
    		rootNode.addChild(aChild);
    		evalUtility(aChild);
    	}
    	//choose best move
    	List<MinMaxNode<int[][][]>> children = rootNode.getChildren();
    	if (children.size() == 0)
    	{
    		int[] move = new int[3];
    		if (color == "green")
    		{
    			move[0] = -1;
    			move[1] = 0;
    			move[2] = 0;
    			task.updateMoveCoord(move);
    		} else
    		{
    			move[0] = 0;
    			move[1] = -1;
    			move[2] = 0;
    			task.updateMoveCoord(move);
    		}
    	} else if (children.size() == 1)
    	{
    		task.updateMoveCoord(children.get(0).getMove());
    	} else
    	{
    		int bestUtility = children.get(0).getUtilValue();
    		task.updateMoveCoord(children.get(0).getMove());
    		for (int i = 0; i < children.size(); i++)
    		{
    			if (children.get(i).getUtilValue() > bestUtility)
    			{
    				task.updateMoveCoord(children.get(0).getMove());
    				bestUtility = children.get(0).getUtilValue();
    			}
    		}
    	}
    	while (timeUp > System.currentTimeMillis())
    	{
    		//waiting for a move to send
    	}
    }
    public void makeBadMove(int boardSize, int[][][] boardState, int[] lastMove, Long maxTime, int[] newMove)
    {
    	Long timeUp = System.currentTimeMillis() + 3500;
    	Timer moveTimer = new Timer();
    	MoveTimerTask2 task = new MoveTimerTask2(newMove);
		moveTimer.schedule(task, 2000);
		
    	decisionTree = new MinMaxTree<int[][][]>(boardState, 3, 0);
    	MinMaxNode<int[][][]> rootNode = decisionTree.getRootNode();
    	List<int[]> moves = getValidMoves(boardState, 0);
    	for (int i = 0; i < moves.size(); i++)
    	{
    		int[][][] newState = new int[boardSize][boardSize][boardSize];
    		newState = copyState(boardState);
    		newState = createState(newState, moves.get(i), 0);
    		List aMove = new ArrayList(3);
    		aMove.add(moves.get(i)[0]);
    		aMove.add(moves.get(i)[1]);
    		aMove.add(moves.get(i)[2]);
    		MinMaxNode<int[][][]> aChild = new MinMaxNode<int[][][]>(newState, aMove, 3, 1);
    		rootNode.addChild(aChild);
    		evalUtility(aChild);
    	}
    	//choose best move
    	List<MinMaxNode<int[][][]>> children = rootNode.getChildren();
    	if (children.size() == 0)
    	{
    		int[] move = new int[3];
    		if (color == "green")
    		{
    			move[0] = -1;
    			move[1] = 0;
    			move[2] = 0;
    			task.updateMoveCoord(move);
    		} else
    		{
    			move[0] = 0;
    			move[1] = -1;
    			move[2] = 0;
    			task.updateMoveCoord(move);
    		}
    	} else if (children.size() == 1)
    	{
    		task.updateMoveCoord(children.get(0).getMove());
    	} else
    	{
    		int bestUtility = children.get(0).getUtilValue();
    		task.updateMoveCoord(children.get(0).getMove());
    		for (int i = 0; i < children.size(); i++)
    		{
    			if (children.get(i).getUtilValue() < bestUtility)
    			{
    				task.updateMoveCoord(children.get(0).getMove());
    				bestUtility = children.get(0).getUtilValue();
    			}
    		}
    	}
    	while (timeUp > System.currentTimeMillis())
    	{
    		//waiting for a move to send
    	}
    }
    public boolean possibleState()
    {
    	List<MinMaxNode<int[][]>> children = decisionTree.getRootNode().getChildren();
    	for (int i = 0; i < children.size(); i++)
    	{
    		if (children.get(i).getChildren().size() > 0)
    			return true; 
    	}
    	return false;
    }
    public int[][][] copyState(int[][][] _state)
    {
    	int[][][] newState = new int[boardSize][boardSize][boardSize];
    	for (int i = 0; i < boardSize; i++)
    	{
    		for (int j = 0; j < boardSize; j++)
    		{
    			for (int k = 0; k < boardSize; k++)
    			{
    				newState[i][j][k] = _state[i][j][k];
    			}
    		}
    	}
    	return newState;
    }
    public boolean equalsState(int[][][] state1, int[][][]state2)
    {
    	for (int i = 0; i < boardSize; i++)
    	{
    		for (int j = 0; j < boardSize; j++)
    		{
    			for (int k = 0; k < boardSize; k++)
    			{
    				if (state1[i][j] != state2[i][j])
    					return false;
    			}
    		}
    	}
    	return true;
    }
    private boolean isValid(int[][][] boardState, int _x, int _y, int _z, int turn)
    {
    	int playerPiece;
    	int otherPlayerPiece;
    	if (turn == 0)
    	{
    		playerPiece = playerSpace;
    		otherPlayerPiece = otherPlayerSpace;
    	} else
    	{
    		playerPiece = otherPlayerSpace;
    		otherPlayerPiece = playerSpace;
    	}
    	boolean valid = false;
		if(boardState [_x][_y][_z] == 0)
		{
			for(int i = -1; i <= 1; i++)
        	{
	        	for(int j = -1; j <= 1; j++)
	        	{
	        		for(int k = -1; k <= 1; k++)
	        		{
						boolean gotOne = false;
						
						System.out.println("checking "+i+", "+j+", "+k); 
						
						int x = _x + i;
						int y = _y + j;
						int z = _z + k;
						
						while(x >= 0 && y >= 0 && z >= 0 && x < boardSize && y < boardSize && z < boardSize)
						{
							if(!gotOne && boardState[x][y][z] == otherPlayerPiece)
							{
								gotOne = true;
							}
							else if(gotOne && boardState[x][y][z] == 0)
							{
								break;
							}
							else if(gotOne && boardState[x][y][z] == playerPiece)
							{
								valid = true;
							}
							
							if (!gotOne)
								break;
							
							x += i;
							y += j;
							z += k;
						}
						//System.out.println(valid);
					}
				}
			}			
		}				
		return valid;
	}
    private List<int[]> getValidMoves(int[][][] boardState, int turn)
    {
    	List<int[]> validMoves = new ArrayList(0);
    	int[] aMove = new int[3];
    	for (int x = 0; x < boardSize; x++)
    	{
    		for (int y = 0; y < boardSize; y++)
    		{
    			for (int z = 0; z < boardSize; z++)
    			{
    				if (isValid(boardState, x, y, z, turn))
    				{
    					aMove[0] = x;
    					aMove[1] = y;
    					aMove[2] = z;
    					validMoves.add(aMove);
    				}
    			}
    		}
    	}
    	return validMoves;
    }   
    private int[][][] createState(int[][][] board, int[] move, int turn)
    {
    	int _x = move[0];
    	int _y = move[1];
    	int _z = move[2];
    	int playerPiece;
    	int otherPlayerPiece;
    	if (turn == 0)
    	{
    		playerPiece = playerSpace;
    		otherPlayerPiece = otherPlayerSpace;
    	} else
    	{
    		playerPiece = otherPlayerSpace;
    		otherPlayerPiece = playerSpace;
    	}
    	for(int i = -1; i <= 1; i++)
        {
	       	for(int j = -1; j <= 1; j++)
	        {
	        	for(int k = -1; k <= 1; k++)
	        	{
					boolean gotOne = false;
					boolean validDir = false;
										
					int x = _x + i;
					int y = _y + j;
					int z = _z + k;
					
					while(x >= 0 && y >= 0 && z >= 0 && x < boardSize && y < boardSize && z < boardSize)
					{
						if(!gotOne && board[x][y][z] == otherPlayerPiece)
						{
							gotOne = true;
						}
						else if(gotOne && (board[x][y][z] == 0) )
						{
							validDir = false;
							break;
						}
						else if(gotOne && board[x][y][z] == playerPiece)
						{
							validDir = true;
							break;
						}
						
						if (!gotOne)
						{
							validDir =  false;
							break;
						}
							
						x += i;
						y += j;
						z += k;
					}
					
					x = _x + i;
					y = _y + j;
					z = _z + k;
					
					while(validDir && x >= 0 && y >= 0 && z >= 0 && x < boardSize && y < boardSize && z < boardSize)
					{
						System.out.println("flipping");
						if(board[x][y][z] != playerPiece && board[x][y][z] != 0)
							board[x][y][z] = playerPiece;
						
						else if(board[x][y][z] == playerPiece)
							break;
										
						x += i;
						y += j;
						z += k;
					}					
				}
			}
		}
		return board;
    }
    public int pieceValue(int[][][] state, int turn)
    {
    	int playerValue = 0;
    	int opponentValue = 0;
    	int playerPiece;
    	int opponentPiece;
    	if (turn == 0)
    	{
    		playerPiece = playerSpace;
    		opponentPiece = otherPlayerSpace;
    	} else
    	{
    		playerPiece = otherPlayerSpace;
    		opponentPiece = playerSpace;
    	}
    	for (int i = 0; i < boardSize; i++)
    	{
    		for (int j = 0; j < boardSize; j++)
    		{
    			for (int k = 0; k < boardSize; k++)
    			{
    				System.out.println(i+" "+j+" "+k);
    				
    				if (state[i][j][k] == playerPiece)
    				{
    					playerValue += boardValues[i][j][k];
    				}
    				else
    				{
    					opponentValue += boardValues[i][j][k];
    				}
    			}
    		}
    	}
    	return (playerValue - opponentValue);
    }
    public boolean isCorner(int x, int y, int z)
    {
    	if (boardValues[x][y][z] == 50)
    		return true;
    	return false;    
    }
    public boolean isSide(int x, int y, int z)
    {
    	if (boardValues[x][y][z] == 3)
    		return true;
    	return false;
    }
    public boolean isEdge(int x, int y, int z)
    {
    	if (boardValues[x][y][z] == 5)
    		return true;
    	return false;
    }
    public boolean isCorX(int x, int y, int z)
    {
    	if ((boardValues[x][y][z] == -10) || (boardValues[x][y][z] == -25))
    		return true;
    	return false;
    }
	public void evalUtility(MinMaxNode<int[][][]> node)
	{
		int utility;
		int[][][] state = node.getState();
		int nodeTurn = node.getTurn();
		int turn;
		if (nodeTurn == 0)
			turn = 1;
		else
			turn = 0;
		int[] aMove = node.getMove();
		int x = aMove[0];
		int y = aMove[1];
		int z = aMove[2];
		utility = pieceValue(state, turn);
		if (isCorner(x, y, z))
			utility += 100;
		if (isSide(x,y,z))
			utility += 20;
		if (isEdge(x,y,z))
			utility += 50;
		if (isCorX(x,y,z))
			utility -=50;
		node.setUtilValue(utility);
	}
}